Resource allocation problems that involve matching of resources available from a service provider to a set of requests from clients for the resources can arise in a variety of different contexts. One example resource allocation problem arises in Internet advertising scenarios, where advertisers may request/buy space for display ads (e.g., graphical “banner” ads) to be shown to users in conjunction with web-pages available from service providers. The service providers may be compensated an amount for each web-page impression (e.g., user view of a page) for which an advertisement is shown. Display ads are typically sold with guaranteed impression goals. In this scenario, the service provider sells orders for a fixed number of impressions and is responsible for making sure that the goals for the orders are met. In this context, the service provider may be concerned with matching of various requests to impressions in a manner that increases revenue and fulfills all the orders.
Matching for the example Internet advertising scenario and other comparable resource allocation problems, though, can become quite difficult as the number of requests to be matched becomes larger due to the number of computations involved in performing the matching. Traditional algorithms suitable to perform matching with relatively small data sets may be unable to successfully perform matching for larger data sets that arise in some scenarios.